import java.util.*;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-04-03
 * Time:14:59
 * Text：无向图最短路径
 */
public class Text20 {
    private int V;
    private List<List<Integer>> list;

    Text20(int v){
        this.V = v;
        list = new ArrayList<>();
        for(int i=0;i<v;i++){
            list.add(new ArrayList<>());
        }
    }
    private void insert(int num1,int num2){
        list.get(num1).add(num2);
        list.get(num2).add(num1);
    }
    private void getShort(int begin,int end){
        int[] array = new int[V];
        Arrays.fill(array,-1);
        array[begin] = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(begin);

        while(!queue.isEmpty()){
            int index = queue.poll();
            List<Integer> ls = list.get(index);
            for(int n : ls){
                if(array[n] == -1){
                    array[n] =array[index] + 1;
                    queue.add(n);
                }
            }
        }
        if(array[end]==-1){
            System.out.println("不存在路径");
            return ;
        }
        System.out.println("该路径为："+begin);
        int cur = begin;
        while(cur != end){
            for(int v : list.get(cur)){
                if(array[v] == array[cur] +1){
                    System.out.println(v+" ");
                    cur = v;
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        Text20 t1 = new Text20(10);
        t1.insert(2,1);
        t1.insert(4,3);
        t1.insert(1,4);
        t1.insert(1,6);
        t1.insert(2,3);
        t1.insert(6,7);
        t1.insert(3,8);
        t1.insert(7,8);
        t1.getShort(1,8);
        System.out.println();
    }
}
